package com.lee.interview.sort;

import java.util.Random;

/**
 * 插入排序：
 *
 */
public class InsertionSort {
	
	public static void main(String[] args) {
		int num = 20;
		int[] sortArr = new int[num];
		Random random = new Random();
		for (int i = 0; i < sortArr.length; i++) {
			sortArr[i] = random.nextInt(num*100);
		}
		
		System.out.println("排序前的数据为：");
		for (int i = 0; i < sortArr.length; i++) {
			System.out.print(sortArr[i]+"	");
		}
		System.out.println();
		
		//排序
		for (int i = 1; i < sortArr.length; i++) {
			int currValue = sortArr[i];
			int j = i;
			while (j>0 && currValue < sortArr[j-1]) {
				// 当前待排序的值小于其前面数组的值，前面的数后移
				sortArr[j] = sortArr[j-1];
				j--;
			}
			sortArr[j] = currValue;
		}
		
		System.out.println("排序后的数据为：");
		for (int i = 0; i < sortArr.length; i++) {
			System.out.print(sortArr[i]+"	");
		}
	}


}
